package sort;

import common.StdOut;
import common.StdRandom;
import common.Stopwatch;

/**
 * @ClassName: SortCompare
 * @Description: 各种排序算法性能测试
 * @Date: 2021/2/26
 * @Author: cakin
 */
public class SortCompare {
    /**
     * 功能描述：算法alg使用的时间
     *
     * @param alg 算法名称
     * @param a   数组
     * @return double 算法使用时间
     * @author cakin
     * @date 2021/2/26
     */
    public static double time(String alg, Comparable[] a) {
        Selection selection = new Selection();
        Insertion insertion = new Insertion();
        Shell shell = new Shell();
        Merge merge = new Merge();
        MergeBU mergebu = new MergeBU();

        Stopwatch timer = new Stopwatch();
        if (alg.equals("Selection")) {
            selection.sort(a);
        }
        if (alg.equals("Insertion")) {
            insertion.sort(a);
        }
        if (alg.equals("Shell")) {
            shell.sort(a);
        }
        if (alg.equals("Merge")) {
            merge.sort(a);
        }
        if (alg.equals("MergeBu")) {
            mergebu.sort(a);
        }

        return timer.elapsedTime();
    }

    /**
     * 功能描述：使用 alg 将T个长度为N的数组排序
     *
     * @param alg 算法
     * @param N   数组长度
     * @param T   进行N次排序
     * @return 排序总时长
     * @author cakin
     * @date 2021/2/26
     */
    public static double timeRandomInput(String alg, int N, int T) {
        double total = 0.0;
        Double[] a = new Double[N];
        for (int t = 0; t < T; t++) {
            // 进行一次测试(生成一个数组并排序)
            for (int i = 0; i < N; i++) {
                a[i] = StdRandom.uniform();
            }
            total += time(alg, a);
        }
        return total;
    }

    /**
     * 功能描述：比较各种排序算法的性能
     *
     * @param args 命令行
     * @author cakin
     * @date 2021/2/26
     */
    public static void main(String[] args) {
        String alg1 = "Selection"; // 选择排序
        String alg2 = "Insertion"; // 插入排序
        String alg3 = "Shell"; // 希尔排序
        String alg4 = "Merge"; // 自顶向下归并排序
        String alg5 = "MergeBu"; // 自底向上归并排序
        int N = 1000;
        int T = 1000;
        double t1 = timeRandomInput(alg1, N, T); // Selection的总时间
        double t2 = timeRandomInput(alg2, N, T); // Insertion的总时间
        double t3 = timeRandomInput(alg3, N, T); // Shell的总时间
        double t4 = timeRandomInput(alg4, N, T); // Merge的总时间
        double t5 = timeRandomInput(alg5, N, T); // MergeBU的总时间

        StdOut.printf("For %d random Doubles  %s is %.4f \n", N, alg1, t1);
        StdOut.printf("For %d random Doubles  %s is %.4f\n", N, alg2, t2);
        StdOut.printf("For %d random Doubles  %s is %.4f\n", N, alg3, t3);
        StdOut.printf("For %d random Doubles  %s is %.4f \n", N, alg4, t4);
        StdOut.printf("For %d random Doubles  %s is %.4f \n", N, alg5, t5);
    }
}
